/*
题目：从中序和后序遍历序列构造二叉树、
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class BuildTreeB {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //如果将中序遍历反序，则得到反向的中序遍历，即每次遍历右孩子，再遍历根节点，最后遍历左孩子
        //如果将后序遍历反序，则得到反向的前序遍历，即每次遍历根节点，再遍历右孩子，最后遍历左孩子
        if (inorder.length == 0 || inorder == null) return null;
        Stack<TreeNode> stack = new Stack<> ();
        int inorderIndex = inorder.length - 1;
        TreeNode root = new TreeNode(postorder[inorderIndex]);
        stack.push(root);

        for (int i = postorder.length - 2; i >= 0; i--) {
            TreeNode tmp = stack.peek();
            if (tmp.val != inorder[inorderIndex]) {
                tmp.right = new TreeNode(postorder[i]);
                stack.push(tmp.right);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    tmp = stack.pop();
                    inorderIndex--;
                }
                tmp.left = new TreeNode(postorder[i]);
                stack.push(tmp.left);
            }
        }

        return root;
    }
}
